package sort;

import java.util.Arrays;

/**
 * 冒泡排序法 O(N^2)
 * 比较相邻的两个元素，进行交换
 */
public class BubbleSort {
    //冒泡排序法
    public static void bubbleSort(int[] arr){
        for(int j = arr.length - 1; j > 0; j--){
            boolean isSwap = false;
            for(int i = 0; i < j; i++){
                if(arr[i] > arr[i+1]){
                    arr[i] = arr[i] + arr[i+1] - (arr[i+1] = arr[i]);
                    isSwap = true;
                }
            }
            if(!isSwap){
                //如果有一趟走完也没有发生交换，则说明已经有序，可以提前退出
                break;
            }
        }
    }

    //测试冒泡排序法
    public static void TestBubbleSort(int[] arr) {
        long start = System.nanoTime();
        bubbleSort(arr);
        long end = System.nanoTime();
        if(SortHelper.isSorted(arr)){
            System.out.println("bubbleSort排序结束，共耗时：" + (end-start)/1000000.0 + "ms");
        }
    }

    public static void main(String[] args) {
        int[] arr = {5,2,3,1,4,9,6,8,7};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
